# -*- coding:utf-8 -*-
class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None
class Solution1:
    # 用两个list表示原链表和现链表
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return None
        pHead_copy = RandomListNode(pHead.label)
        res_pHead = pHead_copy
        pHead_loc = pHead.next
        p_list = [pHead]
        p_list_copy = [pHead_copy]
        while pHead_loc:
            # print('test')
            p_list.append(pHead_loc)
            cur_copy = RandomListNode(pHead_loc.label)

            pHead_copy.next = cur_copy
            pHead_copy = pHead_copy.next
            p_list_copy.append(pHead_copy)
            pHead_loc = pHead_loc.next

        # print(p_list_copy)
        index = 0

        while index < len(p_list):
            if p_list[index].random:
                p_list_copy[index].random = p_list_copy[p_list.index(p_list[index].random)]
            else:
                p_list_copy[index].random = None
            index += 1
        return res_pHead

class Solution2:
    # 用hash表
    def Clone(self, pHead):
        pHead_copy = RandomListNode(pHead.label)
        list_dict = dict()
        list_dict[pHead] = pHead_copy
        curHead = pHead.next
        curHead_copy = pHead_copy
        while curHead:
            curHead_copy.next = RandomListNode(curHead.label)

            curHead_copy = curHead_copy.next
            list_dict[curHead] = curHead_copy
            curHead = curHead.next

        for key, value in list_dict.items():
            if key.random:
                value.random = list_dict[key.random]
            else:
                value.random = None

class Solution3():
    def Clone(self, pHead):
        if not pHead:
            return None

        # cur_node = pHead
        # while cur_node:
        #     print(cur_node.label)
        #     cur_node = cur_node.next
        cur_node = pHead
        while cur_node:
            cur_copy = RandomListNode(cur_node.label)
            next_node = cur_node.next
            cur_node.next = cur_copy
            cur_copy.next = next_node
            cur_node = next_node
        cur_node = pHead
        while cur_node:

            if cur_node.random:
                cur_node.next.random = cur_node.random.next

            cur_node = cur_node.next.next
        res_head = pHead.next
        cur_res = res_head
        cur_node = pHead

        while cur_node:
            # 注意要保证原链表不发生变化
            cur_node.next = cur_node.next.next
            if cur_res.next:
                cur_res.next = cur_res.next.next
            cur_res = cur_res.next
            cur_node = cur_node.next
        cur_res.next = None
        return res_head
a  = RandomListNode(-1)
head = a
for i in range(5):
    a.next = RandomListNode(i)
    a = a.next
test = Solution3()
test_head = test.Clone(head)
while test_head:
    print(test_head.label)
    test_head = test_head.next
